package leetcode.editor.cn.lccup

import kotlin.math.abs

class LCCUP2021 {
    fun purchasePlans(nums: IntArray, target: Int): Int {
        nums.sort()
        var ans = 0
        for (i in 0 until nums.size - 1) {
            if (nums[i] > target / 2) {
                break
            }
            val tempTarget = target - nums[i]
            var left = i + 1
            var right = nums.size - 1
            if (nums[right] <= tempTarget) {
                ans += right - i
                ans %= 1000000007
                continue
            }
            while (left < right) {
                val mid = left + (right - left) / 2
                if (nums[mid] <= tempTarget && nums[mid + 1] > tempTarget) {
                    ans += mid - i
                    ans %= 1000000007
                    break
                } else if (nums[mid] <= tempTarget) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
        }
        return ans
    }

    fun orchestraLayout(num: Int, xPos: Int, yPos: Int): Int {
        var x = 0
        var y = -1
        var cur = 0
        var curDirection = 0 // 0 right 1 down 2 left 3 up
        var step = num
        var round = 1
        while (true) {
            if ((x == xPos && (curDirection == 0 || curDirection == 2)) || (y == yPos && (curDirection == 1 || curDirection == 3)))
                break
            cur += step
            when (curDirection) {
                0 -> {
                    y = num - round
                    step--
                    curDirection = 1
                }
                1 -> {
                    x = num - round
                    curDirection = 2
                }
                2 -> {
                    step--
                    y = round - 1
                    curDirection = 3
                }
                else -> {
                    x = round
                    curDirection = 0
                    round++
                }
            }
            cur %= 9
        }
        cur += if (x == xPos) {
            abs(y - yPos)
        } else {
            abs(x - xPos)
        }
        val ans = cur % 9
        return if (ans == 0) 9 else ans
    }

    fun magicTower(nums: IntArray): Int {
        TODO()
    }
}

fun main() {
    val sol = LCCUP2021()
//    val input1 = intArrayOf(1,2,3,4,5,6,7,8,9,10) // 8 + 6 + 4 + 2
//    println(sol.purchasePlans(input1,10))
    println(sol.orchestraLayout(5, 0, 4))
}